package com.demo.alg.chapter15动态规划.knapsack;

/**
 * 问题描述：给定n种物品和一背包。物品i的重量是w[i]，其价值为v[i]，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
 * 分析：对于一种物品，要么装入背包，要么不装。所以对于一种物品的装入状态可以取0和1。设物品i的装入状态为xi,xi∈
 * (0,1)，此问题称为0-1背包问题。
 * 数据：物品个数n=5,物品重量w[5]={2，2，6，5，4},物品价值v[5]={6，3，5，4，6},总重量c=10
 * 。背包的最大容量为10，那么在设置数组m大小时
 * ，可以设行列值为6和11，那么，对于m(i,j)就表示可选物品为i到n且背包容量为j(总重量)时背包中所放物品的最大价值。
 * （第0位，置为0，不参与计算，只是便于与后面的下标进行统一，无特别用处，也可不这么处理。）
 *
 * http://blog.csdn.net/dapengbusi/article/details/7463968
 */
public class Knapsack {

	static void package0_1(int m[][], int w[], int v[], int n, int c)// n代表物品的个数
	{
		// 采用从底到顶的顺序来设置m[i][j]的值
		// 首先放w[n]
		for (int j = 0; j < c; j++)
			if (j < w[n])
				m[n][j] = 0; // j小于w[n],所对应的值设为0，否则就为可以放置
			else
				m[n][j] = v[n];

		// 对剩下的n-1个物品进行放置。
		int i;
		for (i = n - 1; i >= 1; i--)
			for (int j = 0; j <= c; j++)
				if (j < w[i])
					m[i][j] = m[i + 1][j];// 如果j < w[i]则，当前位置就不能放置，它等于上一个位置的值。
				else
					// 否则：(a)如果把第i个物品装入背包，则背包物品的价值等于第i+1个物品装入容量为j-wi
					// 的背包中的价值加上第i个物品的价值vi;
					// (b)如果第i个物品没有装入背包，则背包中物品价值就等于把前i+1个物品装入容量为j的背包中所取得的价值。显然，取二者中价值最大的作为把前i个物品装入容量为j的背包中的最优解。
					m[i][j] = m[i + 1][j] > m[i + 1][j - w[i]] + v[i] ? m[i + 1][j]
							: m[i + 1][j - w[i]] + v[i];
	}

}